package com.justnow.offer;



/**
 * @author justnow
 * Created on 2020-08-18
 * Description
 * 01背包问题
 */
public class Solution10_1 {

    /**
     *
     * @param W，背包可以承受的最大重量
     * @param N，物品的总个数
     * @param weights，物品重量数组
     * @param values，物品价值数组
     * @return
     */
    public int knapsack(int W, int N, int[] weights, int[] values) {
        //dp[i][j]，表示前i件物品重量不超过j的情况下能达到的最大价值
        int[][] dp = new int[N+1][W+1];
        //i表示，第i个商品
        for (int i = 1; i <= N; i++) {

            //定义包能承受的重量为j，让j从1开始到W，分别得到j为不同值的情况下的dp值
            for (int j = 1; j <= W; j++) {
                // 如果包能承受的重量j，小于当前商品的重量，那么当期那商品价不添加；
                // 否则进行，此时需要进行判断
                if (j < weights[i - 1]) {
                    dp[i][j] =  dp[i - 1][j];
                } else {
                    dp[i][j] =  Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                }
            }
        }

        return dp[N][W];
    }

    public static void main(String[] args) {
        Solution10_1 solution10_1 = new Solution10_1();
        int knapsack = solution10_1.knapsack(8, 4, new int[]{2, 3, 4, 5}, new int[]{3, 4, 5, 6});
        System.out.println(knapsack);
    }
}
